#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 数据结构定义
typedef struct {
    int weight;
    double value;
    double ratio; // 价值密度
} Item;

typedef struct {
    int *selected;
    double total_value;
    int total_weight;
    double time_cost;
} Result;

// 从文件读取测试数据
Item* load_test_data(const char* filename, int* n) {
    FILE *file = fopen(filename, "r");
    if (file == NULL) {
        printf("无法打开文件 %s\n", filename);
        return NULL;
    }
    
    // 读取物品数量
    fscanf(file, "%d", n);
    
    // 分配内存并读取物品数据
    Item *items = malloc(*n * sizeof(Item));
    
    for (int i = 0; i < *n; i++) {
        fscanf(file, "%d %lf", &items[i].weight, &items[i].value);
        items[i].ratio = items[i].value / items[i].weight;
    }
    
    fclose(file);
    return items;
}

// 贪心法求解0-1背包问题
Result greedy_knapsack(Item items[], int n, int capacity) {
    Result result = {0};
    result.selected = calloc(n, sizeof(int));
    
    // 创建索引数组用于排序
    int *indices = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        indices[i] = i;
    }
    
    // 按价值密度降序排序索引（冒泡排序）
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (items[indices[j]].ratio < items[indices[j + 1]].ratio) {
                int temp = indices[j];
                indices[j] = indices[j + 1];
                indices[j + 1] = temp;
            }
        }
    }
    
    // 贪心选择
    for (int i = 0; i < n; i++) {
        int idx = indices[i];
        if (result.total_weight + items[idx].weight <= capacity) {
            result.selected[idx] = 1;
            result.total_weight += items[idx].weight;
            result.total_value += items[idx].value;
        }
    }
    
    free(indices);
    return result;
}

// 输出结果到文件
void output_result_to_file(const char* filename, Item items[], int n, Result result) {
    FILE *file = fopen(filename, "w");
    if (file == NULL) {
        printf("无法创建输出文件 %s\n", filename);
        return;
    }
    
    // 输出选择的物品
    fprintf(file, "选择的物品（编号 重量 价值）:\n");
    for (int i = 0; i < n; i++) {
        if (result.selected[i]) {
            fprintf(file, "%d %d %.2f\n", i + 1, items[i].weight, items[i].value);
        }
    }
    
    // 输出总重量、总价值和时间开销
    fprintf(file, "总重量: %d\n", result.total_weight);
    fprintf(file, "总价值: %.2f\n", result.total_value);
    fprintf(file, "时间开销: %.6f 秒\n", result.time_cost);
    
    fclose(file);
}

int main() {
    printf("=== 贪心法测试器 ===\n");
    
    // 物品数量数组
    int item_counts[] = {1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 
                        20000, 40000, 80000, 160000, 320000};
    int num_item_counts = sizeof(item_counts) / sizeof(item_counts[0]);
    
    // 背包容量数组
    int capacities[] = {10000, 100000, 1000000};
    int num_capacities = sizeof(capacities) / sizeof(capacities[0]);
    
    printf("开始贪心法测试...\n\n");
    
    // 对每个物品数量
    for (int i = 0; i < num_item_counts; i++) {
        int item_count = item_counts[i];
        char data_filename[100];
        sprintf(data_filename, "items_%d.txt", item_count);
        
        printf("加载数据文件: %s\n", data_filename);
        
        int n;
        Item *items = load_test_data(data_filename, &n);
        
        if (items == NULL) {
            printf("跳过文件: %s\n", data_filename);
            continue;
        }
        
        // 对每个背包容量进行测试
        for (int j = 0; j < num_capacities; j++) {
            int capacity = capacities[j];
            
            printf("  测试容量 %d: ", capacity);
            
            clock_t start = clock();
            Result result = greedy_knapsack(items, n, capacity);
            clock_t end = clock();
            
            result.time_cost = ((double)(end - start)) / CLOCKS_PER_SEC;
            
            // 生成输出文件名
            char output_filename[200];
            sprintf(output_filename, "greedy_%d_%d.txt", item_count, capacity);
            
            output_result_to_file(output_filename, items, n, result);
            
            printf("完成 (%.6f秒, 价值=%.2f)\n", result.time_cost, result.total_value);
            
            if (result.selected != NULL) {
                free(result.selected);
            }
        }
        
        free(items);
        printf("\n");
    }
    
    printf("贪心法测试完成！\n");
    return 0;
}